#include "Sort.h"

void PrintArray(int* a, int n)
{
    for (int i = 0; i < n; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void InsertSort(int* a, int n)
{
    for (int i = 0; i < n - 1; ++i)
    {
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0)
        {
            if (tmp < a[end])
            {
                a[end + 1] = a[end];
                --end;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

//void ShellSort(int* a, int n)
//{
//    /*int gap = 3;*/
//
//    /*for (int j = 0; j < gap; ++j)
//    {
//        for (int i = j; i < n - gap; i += gap)
//        {
//            int end = i;
//            int tmp = a[end + gap];
//            while (end >= 0)
//            {
//                if (tmp < a[end])
//                {
//                    a[end + gap] = a[end];
//                    end -= gap;
//                }
//                else
//                {
//                    break;
//                }
//            }
//            a[end + gap] = tmp;
//        }
//    }*/
//
//
//    int gap = n;
//    while (gap > 1)
//    {
//        gap = gap / 3 + 1;
//        //gap = gap / 2;
//
//        for (int i = 0; i < n - gap; ++i)
//        {
//            int end = i;
//            int tmp = a[end + gap];
//            while (end >= 0)
//            {
//                if (tmp < a[end])
//                {
//                    a[end + gap] = a[end];
//                    end -= gap;
//                }
//                else
//                {
//                    break;
//                }
//            }
//            a[end + gap] = tmp;
//        }
//
//        //printf("gap:%d->", gap);
//        //PrintArray(a, n);
//    }
//}

void ShellSort(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1;
        //gap = gap / 2;

        for (int i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}



void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}


void AdjustDwon(int* a, int size, int parent)
{
    int child = parent * 2 + 1;
    while (child < size)
    {
        
        if (child + 1 < size && a[child + 1] > a[child])
        {
            ++child;
        }

        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}


void HeapSort(int* a, int n)
{
    for (int i = (n - 1 - 1) / 2; i >= 0; --i)
    {
        AdjustDwon(a, n, i);
    }

    // O(N*logN)
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDwon(a, end, 0);
        --end;
    }
}

void SelectSort(int* a, int n)
{
    assert(a);
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        int mini = begin, maxi = begin;
        for (int i = begin + 1; i <= end; ++i)
        {
            if (a[i] < a[mini])
                mini = i;

            if (a[i] > a[maxi])
                maxi = i;
        }
        Swap(&a[begin], &a[mini]);

        if (begin == maxi)
        {
            maxi = mini;
        }

        Swap(&a[end], &a[maxi]);
        ++begin;
        --end;
    }
}


void BubbleSort(int* a, int n)
{
    assert(a);

    for (int j = 0; j < n - 1; ++j)
    {
        int exchange = 0;
        for (int i = 1; i < n - j; ++i)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }

        if (exchange == 0)
        {
            break;
        }
    }
}

// [begin, end]
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
    
    int key = right;//选定基准值
    while (left < right)
    {
        //选右边为基准值，左指针先走
        while (left < right && a[left] <= a[key])
        {
            left++;
        }
 
        //右指针再走
        while (left < right && a[right] >= a[key])
        {
            right--;
        }
 
        Swap(&a[left], &a[right]);
    }
    Swap(&a[left], &a[key]);
    return left;
}
 

// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
    int key = a[left];//取出基准值
    int hole = left;//保存坑的位置
    while (left < right)
    {
        while (left < right && a[right] >= key)
        {
            right--;
        }
        a[hole] = a[right];
        hole = right;
 
        while (left < right && a[left] <= key)
        {
            left++;
        }
        a[hole] = a[left];
        hole = left;
    }
    a[hole] = key;
    return hole;
}

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
    //1.将基准值定在left
    int keyi = left;
    int prev = left;
    int cur =  left + 1;
    while (cur <= right)
    {
        if (a[cur] < a[keyi] && ++prev != cur)
        {
            Swap(&a[prev], &a[cur]);
        }
        cur++;
        
    }
    Swap(&a[prev], &a[keyi]);

    //2.将基准值定在right
    /*int keyi = right;
    int prev = left - 1;
    int cur = prev + 1;
    while (cur <= right)
    {
        if (a[cur] < a[keyi] && ++prev != cur)
        {
            Swap(&a[cur], &a[prev]);
        }
        cur++;
    }
    Swap(&a[keyi], &a[++prev]);*/
    return prev;
}

void QuickSort(int* a, int begin, int end)
{
    assert(a);
    if (begin >= end)
    {
        return;
    }
 
    
    int keyi = PartSort1(a, begin, end);
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
    
 
}

//三数取中
 
int MidIndex(int* a, int left, int right)
{
    int mid = (left + right) / 2;
    //防止mid越界
    //int mid = left+(right - left) / 2;
 
    if (a[left] < a[right])
    {
        if (a[mid] < a[left])
        {
            return left;
        }
        else if (a[mid] > a[right])
        {
            return right;
        }
        else
        {
            return mid;
        }
    }
    else
    {
        if (a[mid] > a[left])
        {
            return left;
        }
        else if (a[mid] < a[right])
        {
            return right;
        }
        else
        {
            return mid;
        }
    }
}



// 快速排序 非递归实现

void StackInit(ST* ps)
{
    assert(ps);
    //初始化
    ps->a = NULL;
    ps->top = 0;
    ps->capacicy = 0;
}




void StackPush(ST* ps, STDatatype x)
{
    assert(ps);
    //检查空间，满了就增容
    if (ps->top == ps->capacicy)
    {
        //第一次开辟空间容量为4，其它次容量为当前容量*2
        int newcapacity = ps->capacicy == 0 ? 4 : ps->capacicy * 2;
        //第一次开辟空间，a指向空，realloc的效果同malloc
        STDatatype* tmp = realloc(ps->a, sizeof(STDatatype) * newcapacity);
        //检查realloc
            //realloc失败
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
            //realloc成功
        ps->a = tmp;
        ps->capacicy = newcapacity;
    }
    //插入数据
    ps->a[ps->top] = x;
    ps->top++;
}
bool StackEmpty(ST* ps)
{
    assert(ps);
    //等于0是真，否则为假
    return ps->top == 0;
}
void StackPop(ST* ps)
{
    assert(ps);
    //删除的话得保证指向的空间不为空
    assert(!StackEmpty(ps));
    //删除
    --ps->top;
}
int StackSize(ST* ps)
{
    assert(ps);
    //此时的top就是长度
    return ps->top;
}
STDatatype StackTop(ST* ps)
{
    assert(ps);
    //找栈顶的话得保证指向的空间不为空
    assert(!StackEmpty(ps));
    //此时的top-1就是栈顶数据
    return ps->a[ps->top - 1];
}
void StackDestory(ST* ps)
{
    assert(ps);
    //a为真代表它指向动态开辟的空间
    if (ps->a)
    {
        free(ps->a);
    }
    ps->a = NULL;
    ps->top = 0;
    ps->capacicy = 0;
}


void QuickSortNonR(int* a, int left, int right)
{
    //创建栈
    struct Stack st;
    StackInit(&st);
 
    //原始数组区间入栈
    StackPush(&st, right);
    StackPush(&st, left);
 
    //将栈中区间排序
    while (!StackEmpty(&st))
    {
        //注意：如果right先入栈，栈顶为left
        left = StackTop(&st);
        StackPop(&st);
        right = StackTop(&st);
        StackPop(&st);
        
        //得到基准值
        int mid = PartSort3(a, left, right);
 
        // 以基准值为分割点，形成左右两部分
        if (right > mid+1)
        {
            StackPush(&st, right);
            StackPush(&st, mid + 1);
        }
        if (left < mid - 1)
        {
            StackPush(&st, mid - 1);
            StackPush(&st, left);
        }
    }
    StackDestory(&st);
}

void _MergeSort(int* a, int left, int right,int* tmp)
{
    //区间中没有元素时不再合并
    if (left >= right)
    {
        return;
    }
 
    //划分数组，每次一分为二
    int mid = (left + right) / 2;
    _MergeSort(a, left, mid,tmp);//划分左区间
    _MergeSort(a, mid + 1, right,tmp);//划分右区间
 
    //合并有序序列
    int begin1 = left, end1 = mid;//有序序列1
    int begin2 = mid + 1, end2 = right;//有序序列2
    int i = left;
    while (begin1 <= end1 && begin2 <= end2)//注意结束条件为一个序列为空时就停止
    {
        if (a[begin1] < a[begin2])
        {
            tmp[i++] = a[begin1++];
        }
        else
        {
            tmp[i++] = a[begin2++];
        }
    }
 
    //两序列不可能同时为空，将剩余元素合并
    while (begin1 <= end1)
    {
        tmp[i++] = a[begin1++];
    }
 
    while (begin2 <= end2)
    {
        tmp[i++] = a[begin2++];
    }
 
    //将合并后的序列拷贝到原数组中
    //在这里拷贝的原因是 保证返回到上一层递归后两个子序列中的元素是有序的
    int j = 0;
    for (j = left; j <= right; j++)
    {
        a[j] = tmp[j];
    }
}
 
// 归并排序递归实现
void MergeSort(int* a, int n)
{
    assert(a);
    //因为需要将两个有序序列合并，需借助额外数组
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc");
        exit(-1);
    }
 
    _MergeSort(a, 0, n - 1,tmp);
 
    free(tmp);
    tmp = NULL;
}

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
    assert(a);
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc");
        exit(-1);
    }
 
    //初始化每组的元素个数为1
    int gap = 1;
    while (gap < n)//gap为n时就只有一个序列了，所以gap<n
    {
        //归并每两组归并一次
        int index = 0; //记录tmp数组中的元素下标
        for (int i = 0; i < n; i+=2*gap)//两组中的元素个数为2*gap
        {
            //控制两组边界
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            
            //当原数组中元素个数不是2^n时，最后两组组会出现元素不匹配的情况
            //情况1：end1>=n或begin2>=n,即最后两组中只有一组有元素，则不需归并
            if (end1 >= n || begin2 >= n)
            {
                break;
            }
            //情况2：end2>=n，即最后两组中，第二组元素个数小于第一组，则需要调整第二组边界
            if (end2 >= n)
            {
                end2 = n - 1;
            }
 
            //归并
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (a[begin1] < a[begin2])
                {
                    tmp[index++] = a[begin1++];
                }
                else
                {
                    tmp[index++] = a[begin2++];
                }
            }
 
            while (begin1 <= end1)
            {
                tmp[index++] = a[begin1++];
            }
 
            while (begin2 <= end2)
            {
                tmp[index++] = a[begin2++];
            }
 
            
        }
        //一趟排完后，将归并后的有序序列拷贝到原数组中
        for (int j = 0; j < index; j++)
        {
            a[j] = tmp[j];
        }
        //每次循环每组元素个数增大2倍
        gap *= 2;
    }
 
    free(tmp);
    tmp = NULL;
}

// 计数排序
void CountSort(int* a, int n)
{
    assert(a);
    // 创建计数数组，数组大小为原数组中最大值-最小值+1
    int max = a[0], min = a[0];
    int i = 0;
    for (i = 0; i < n; i++)
    {
        if (a[i] > max)
        {
            max = a[i];
        }
        if (a[i] < min)
        {
            min = a[i];
        }
    }
    int range = max - min + 1;
    int* count = (int*)malloc(sizeof(int) * range);
    // 初始化计数数组为0
    memset(count, 0, range * 4);
 
    // 统计次数
    for (i = 0; i < n; i++)
    {
        count[a[i] - min]++;
    }
    // 根据次数，进行排序
    int j = 0;
    for (i = 0; i < range; i++)
    {
        while (count[i]--)
        {
            a[j++] = i+min;
        }
    }
    free(count);
    count = NULL;
}



